import java.util.ArrayList;
import java.util.Arrays;

public class Wu_4_22 {
    public static void main(String[] args) {
        // creating array must be Character,char will be an error
        //泛型需要传入一个类，char不是类，Character才是
        //确定唯一的二叉树必须要有中序inSeq，
        //inSeq确认头节点左右各有多少元素，preSeq、postSeq确认头节点的位置
        //preSeq和postSeq一起不能确认唯一的二叉树
        ArrayList<Character>preSeq=new ArrayList<>(
            Arrays.asList(new Character[]{'F','B','A','D','C','E','G','I','H'}));

        ArrayList<Character>inSeq=new ArrayList<>(
            Arrays.asList(new Character[]{'A','B','C','D','E','F','G','H','I'}));

        System.out.println("-----------");
        TreeNode root=new Wu_4_22().buildBT(preSeq, inSeq);
        System.out.println(root.key);
        System.out.println("-----------------");
        new Wu_4_22().inorder(root);
    }

    void preorder(TreeNode root){
        if(root == null)
             return;
        System.out.println(root.key);
        preorder(root.left);
        preorder(root.right);
    }
    void inorder(TreeNode root){
        if(root == null)
             return;
        inorder(root.left);
        System.out.println(root.key);
        inorder(root.right);
    }
    void postorder(TreeNode root){
        if(root == null)
             return;
        postorder(root.left);
        postorder(root.right);
        System.out.println(root);
    }
    TreeNode buildBT(ArrayList<Character> preSeq,ArrayList<Character> inSeq){
        // determine if the recursion is ends
        if(preSeq.size()==1)
            return new TreeNode(preSeq.get(0));
        TreeNode root=new TreeNode(preSeq.get(0));
        
        ArrayList<Character>leftpreSeq =new ArrayList<>();
        ArrayList<Character>rightpreSeq =new ArrayList<>();
    
        ArrayList<Character>leftinSeq =new ArrayList<>();
        ArrayList<Character>rightinSeq =new ArrayList<>();
    
        //split inseq
            // [ ) subList
        leftinSeq=new ArrayList<>(inSeq.subList(0,inSeq.indexOf(root.key)));
        rightinSeq=new ArrayList<>(inSeq.subList(inSeq.indexOf(root.key)+1,inSeq.size()));
    
        //split preseq
        leftpreSeq=new ArrayList<>(preSeq.subList(1, leftinSeq.size()+1));
        rightpreSeq=new ArrayList<>(preSeq.subList(leftinSeq.size()+1,preSeq.size()));
      
        //connect the root and its left and right node
        
        if(leftpreSeq.size() != 0)
             root.left=new TreeNode(leftpreSeq.get(0));
        if(rightpreSeq.size()!=0)
             root.right=new TreeNode(rightpreSeq.get(0));

        // recursion 
        if(leftpreSeq.size()!=0 && leftinSeq.size()!=0)
             root.left = buildBT(leftpreSeq, leftinSeq);
        if(rightpreSeq.size()!=0 && rightinSeq.size()!=0)
             root.right = buildBT(rightpreSeq, rightinSeq);
        return root;

    }
}
class TreeNode{
    char key;
    TreeNode left;
    TreeNode right;
    public TreeNode(char key){
        this.key=key;
        left=right=null;
    }
}


